/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-in-rotated-sorted-array
   @Language: C++
   @Datetime: 16-02-09 08:29
   */

class Solution {
	/** 
	 * param A : an integer ratated sorted array
	 * param target :  an integer to be searched
	 * return : an integer
	 * 4 status
	 * origin is in ascending : 6 1 2 3 4 5
	 *                          2 3 4 5 6 1
	 * origin is in descending: 5 4 3 2 1 6
	 *                          1 6 5 4 3 2
	 */
public:
	int search(vector<int> &A, int target) {
		// write your code here
		int begin=0, end=A.size(), mid;
		if (end<1) return -1;
		while(begin<end){
			mid = (end-begin)/2+begin;
			if(A[mid]==target) return mid;
			if (A[begin]<=A[mid]){
				if (A[mid]>=target && A[begin]<=target) end=mid;
				else begin=mid+1;
			}
			else{
				if (A[mid]<=target && A[end-1]>=target) begin=mid+1;
				else end=mid;
			}
		}
		return (A[mid]==target ? mid:-1);
	}
};
